package cn.ac.iscas.algorithm;

import java.util.Vector;

/**
 * @author Simon@itechs
 * based on max-heap, the priority should be above 0
 */
public class PriorityQueue {
	private Vector<Prioritized> heap = new Vector<Prioritized>();
	
	public void put(Prioritized newobj){
		heap.add(newobj);
		heapfy(heap.size() - 1);
	}
	
	public Prioritized extractMax(){
		Prioritized max = heap.get(0);
		max.setPriority(-0.5);
		int parent = 0;
		double parentP = heap.get(parent).getPriority();
		double leftP = getLeftPriority(parent);
		double rightP = getRightPriorty(parent);
		while ((parentP < leftP) || (parentP < rightP)){
			if (leftP > rightP){
				int left = getLeftIndex(parent);
				swap(parent, left);
				parent = left;
				leftP = getLeftPriority(parent);
				rightP = getRightPriorty(parent);
			} else {
				int right = getRightIndex(parent);
				swap(parent, right);
				parent = right;
				leftP = getLeftPriority(parent);
				rightP = getRightPriorty(parent);				
			}
		}
		heap.remove(max);
		return max;
	}
	
	private void swap(int i, int j){
		Prioritized tmp = heap.get(i);
		heap.set(i, heap.get(j));
		heap.set(j, tmp);
	}
	
	private void heapfy(int i){
		int child = i;
		double childP = heap.get(child).getPriority();
		double parentP = getParentPriority(i);
		while (childP > parentP){
			int parent = getParentIndex(child);
			swap(child, parent);
			child = parent;
			parentP = getParentPriority(child);
		}
	}
	
	private int getParentIndex(int i){
		int parent = (i - 1) / 2;
		if (parent >= 0) return parent;
		return -1;
	}
	
	private int getLeftIndex(int i){
		int left = (i + 1) * 2 - 1;
		if (left < heap.size()) return left;
		return -1;
	}
	
	private int getRightIndex(int i){
		int right = (i + 1) * 2 ;
		if (right < heap.size()) return right;
		return -1;
	}
	
	private double getLeftPriority(int i){
		int left = (i + 1) * 2 - 1;
		if (left < heap.size()) return heap.get(left).getPriority();
		return -1;
	}
	
	private double getRightPriorty(int i){
		int right = (i + 1) * 2 ;
		if (right < heap.size()) return heap.get(right).getPriority();
		return -1;
	}
	
	private double getParentPriority(int i){
		int parent = (i - 1) / 2;
		if (parent >= 0) return heap.get(parent).getPriority();
		return Double.MAX_VALUE;	
	}
	
	public boolean isEmpty(){
		if (heap.size() == 0) return true;
		else return false;
	}
}
